package bishizhuanyong.腾讯音乐;

import Niuke.Tree;
import SortTable.HeapSort;

import java.util.*;



//https://www.nowcoder.com/discuss/1045588?channel=-1&source_id=discuss_terminal_discuss_history_nctrack&ncTraceId=14f78cc86b074bd0946b39c7c35f148b.590.16626426681524131
//上面是牛客上的题解



//今天感觉状态不好，题不是很难，但是自己做的不好，哎。
public class Main {



    public static int minOperations (String str) {
        // write code here
        if (str.length()==0||str==" ")
            return 0;
        int[] arr=new int[26];
        for (int i=0;i<str.length();i++)
            arr[str.charAt(i)-'a']++;
        HashSet<Integer> empty=new HashSet<>();
        HashSet<Integer> ou=new HashSet<>();
        for (int i=0;i<arr.length;i++){
            if (arr[i]==0)
                empty.add(i);
            if (arr[i]%2==0)
                ou.add(i);
        }
        int res=0;
        while (!no_repeat(arr)){
            for (int i=0;i<arr.length&&!no_repeat(arr);i++){
                if (arr[i]>1){
                    int count=arr[i]/2;
                    res+=count;
                    arr[i]=1;
                    while (count!=0){
                        if (empty.size()>=count){
                            Iterator<Integer> iterator = empty.iterator();
                            for (int j=0;j<count;j++) {
                                Integer next = iterator.next();
                                arr[next]++;
                                iterator.remove();
                            }
                            count=0;
                        }else {
                            //0
                            int temp=count-empty.size();
                            Iterator<Integer> iterator = empty.iterator();
                            int size=empty.size();
                            for (int j=0;j<size;j++) {
                                Integer next = iterator.next();
                                arr[next]++;
                                iterator.remove();
                            }
                            //偶数
                            int rsize=ou.size();
                            int size1 =Math.min(temp,ou.size());
                            Iterator<Integer> iterator1 = ou.iterator();
                            for (int n=0;n<size1;n++){
                                Integer next = iterator1.next();
                                arr[next]++;
                                iterator1.remove();
                            }
                            //一般数
                            if (size1==rsize){
                                int n=temp-rsize;
                                for (int k=0;k<n;k++){
                                    arr[k]++;
                                    if (arr[k]%2==0)
                                        ou.add(k);
                                }
                            }


                        }
                    }
                }
            }
        }
        return res;
    }

    public static boolean no_repeat(int[] arr){
        for (int i=0;i<arr.length;i++){
            if (arr[i]>=2)
                return false;
        }
        return true;
    }





    class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode(int val) {
          this.val = val;
        }
    }


    public int getTreeSum (TreeNode tree) {
        // write code here
        return 0;
    }



    public ArrayList<TreeNode> getBinaryTrees (ArrayList<Integer> preOrder, ArrayList<Integer> inOrder) {
        // write code here
        return create(preOrder,inOrder,0,preOrder.size()-1,0,inOrder.size()-1);
    }

    public ArrayList<TreeNode> create(ArrayList<Integer> pre,ArrayList<Integer> in,int p1,int p2,int i1,int i2){
        if (pre==null||p2-p1>=0)
            return null;
        Integer root_val = pre.get(0);
        ArrayList<TreeNode> res=new ArrayList<>();
        for (int i=0;i<p2;i++){
            if (in.get(i)==root_val){
                ArrayList<TreeNode> leftc=create(pre,in,p1+1,p1+1+i,i1,i-1);
                ArrayList<TreeNode> rightc = create(pre, in,p1+1+i+1,p2,i+1,i2);
                for (int m=0;m<leftc.size();m++){
                    for (int n=0;n<rightc.size();n++){
                        TreeNode root=new TreeNode(root_val);
                        root.left=leftc.get(m);
                        root.right=rightc.get(n);
                        res.add(root);
                    }
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        ArrayList<Integer> pre= new ArrayList<>();
        pre.add(1);
        pre.add(1);
        pre.add(2);
        ArrayList<Integer> in= new ArrayList<>();
        in.add(1);
        in.add(2);
        in.add(1);
        new Main().getBinaryTrees(pre,in);

    }



}
